package com.murphy.algorithm.tree;

/**
 * 二叉树
 * @author dongsufeng
 * @date 2020/9/24 17:05
 * @version 1.0
 */
public class BinaryTree {

	public static class Node<E>{
		private E e;
		private Node<E> left;
		private Node<E> right;

		public Node(E e){
			this.e=e;
			this.left=null;
			this.right=null;
		}
	}
	private Node<Integer> tree;
	public void insert(int item){
		if (tree==null){
			tree=new Node<>(item);
			return;
		}
		Node<Integer> node=tree;
		while (node!=null){
			if (item>node.e){
				if (node.right==null){
					node.right=new Node<>(item);
					return;
				}
				node=node.right;
			}else {
				if (item<node.e){
					if (node.left == null){
						node.left=new Node<>(item);
						return;
					}
					node=node.left;
				}
			}
		}
	}
	public int find(int value){
		Node<Integer> node=tree;
		while (node != null){
			if (node.e>value){
				node=node.left;
			}else if (node.e < value){
				node=node.right;
			}else {
				return value;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int [] items={2,1,4,5,6,3,7,9,8};
		BinaryTree binaryTree = new BinaryTree();
		for (int item : items) {
			binaryTree.insert(item);
		}
		Node<Integer> tree = binaryTree.tree;

		binaryTree.printTree(tree);
		System.out.println(binaryTree.find(1));
	}
	public void printTree(Node<Integer> tree){
		if (tree==null){
			return;
		}
		printTree(tree.left);
		System.out.println(tree.e);
		printTree(tree.right);
	}
}
